package org.lql.algo.codecrush.hot100.linked;

import org.lql.algo.common.ListNode;

/**
 * @author: liangqinglong
 * @date: 2025-10-04 00:46
 * @description: 234. 回文链表 <a href="https://leetcode.cn/problems/palindrome-linked-list/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class IsPalindrome {

	public boolean isPalindrome(ListNode head) {
		if (head == null || head.next == null) {
			return true;
		}
		// 快慢指针，快指针遍历结束，慢指针恰好到中点
		ListNode fast = head;
		ListNode slow = head;
		while (fast != null && fast.next != null) {
			fast = fast.next.next;
			slow = slow.next;
		}
		// 翻转后半部分链表
		ListNode last = null;
		while (slow != null) {
			ListNode next = slow.next;
			slow.next = last;
			last = slow;
			slow = next;
		}
		// 比较前后两段链表
		ListNode p = head;
		while (last != null) {
			if (p.val != last.val) {
				return false;
			}
			p = p.next;
			last = last.next;
		}
		return true;
	}

	public static void main(String[] args) {
		ListNode head = new ListNode(1, new ListNode(2, new ListNode(2, new ListNode(1))));
		System.out.println(new IsPalindrome().isPalindrome(head));
	}
}
